Introduction

• Divisibility rules often feel like clever shortcuts.
• Many people learn them early on, but rarely see why they work.
• Using congruence and place value, we can finally explain the logic behind these rules.

What Divisibility Really Means

• A number $n$ is divisible by $d$ if: $$n = dk \quad\text{for some integer } k.$$
• Equivalent statement: $$n \equiv 0 \pmod{d}.$$
• Divisibility tests help us check this without performing long division.

Key idea:

• If we can rewrite $n$ in a simpler form modulo $d$, we can test divisibility quickly.

A Quick Review of Congruence

• We write $$a \equiv b \pmod{m}$$ when $a$ and $b$ leave the same remainder upon division by $m$.
• Useful properties:
  • Addition: $$a \equiv b \Rightarrow a+c \equiv b+c.$$
  • Multiplication: $$a \equiv b \Rightarrow ac \equiv bc.$$
  • Powers: $$a \equiv b \Rightarrow a^k \equiv b^k.$$

These rules let us replace powers of 10 with simpler numbers.

Why Congruence Explains Divisibility Tests

Every whole number can be written as: $$n = a_0 + 10a_1 + 10^2 a_2 + 10^3 a_3 + \cdots$$ If we know what $10$, $10^2$, $10^3$, etc. are congruent to modulo $d$, we can replace them with simpler values.

This leads to rules involving:

• the last digit,
• the last two or three digits,
• the sum of digits,
• alternating sums,
• or other patterns.

Divisibility by 2, 5, and 10: Place Value at Work

These are the simplest divisibility rules because 10 is a multiple of 2, 5, and 10.
That means powers of 10 behave very simply modulo these numbers.

Divisibility by 2

Key idea

• $10 \equiv 0 \pmod{2}$
• So $10^k \equiv 0$ for all $k \ge 1$.

This means every digit except the last contributes a multiple of 2.

Rule

• A number is divisible by 2 iff its last digit is even.

Examples

• 134 → last digit 4 → even → divisible by 2
• 2,571 → last digit 1 → odd → not divisible by 2
• 90 → last digit 0 → divisible by 2

Divisibility by 5

Key idea

• $10 \equiv 0 \pmod{5}$
• So only the last digit matters.

Rule

• A number is divisible by 5 iff its last digit is 0 or 5.

Examples

• 245 → ends in 5 → divisible by 5
• 1,380 → ends in 0 → divisible by 5
• 1,237 → ends in 7 → not divisible by 5

Divisibility by 10

Key idea

• $10 \equiv 0 \pmod{10}$
• So the number must end in 0.

Rule

• A number is divisible by 10 iff its last digit is 0.

Examples

• 430 → ends in 0 → divisible by 10
• 1,002 → ends in 2 → not divisible by 10

Divisibility by 3 and 9: The Sum‑of‑Digits Rule

These rules come from the fact that 10 behaves like 1 modulo 3 and 9.

Why the rule works

Key congruences

• $10 \equiv 1 \pmod{3}$
• $10 \equiv 1 \pmod{9}$

So: $$10^k \equiv 1^k \equiv 1.$$ This means: $$n = a_0 + 10a_1 + 10^2 a_2 + \cdots \equiv a_0 + a_1 + a_2 + \cdots$$ The number is congruent to the sum of its digits.

Divisibility by 3

Rule

• A number is divisible by 3 iff the sum of its digits is divisible by 3.

Examples

• 372
  • Digit sum: $3+7+2 = 12$
  • $12$ divisible by 3 → so 372 is divisible by 3
• 1,048
  • Digit sum: $1+0+4+8 = 13$
  • 13 not divisible by 3 → not divisible by 3

Divisibility by 9

Rule

• A number is divisible by 9 iff the sum of its digits is divisible by 9.

Examples

• 729
  • Digit sum: $7+2+9 = 18$
  • 18 divisible by 9 → so 729 is divisible by 9
• 5,432
  • Digit sum: $5+4+3+2 = 14$
  • 14 not divisible by 9 → not divisible by 9

Divisibility by 11: Alternating Sums and Patterns

This rule comes from the fact that 10 behaves like −1 modulo 11.

Why the rule works

Key congruence

• $10 \equiv -1 \pmod{11}$

So:

• $10^0 \equiv 1$
• $10^1 \equiv -1$
• $10^2 \equiv 1$
• $10^3 \equiv -1$
• … alternating forever.

Thus: $$n \equiv a_0 - a_1 + a_2 - a_3 + \cdots \pmod{11}.$$

Rule

A number is divisible by 11 iff the alternating sum of its digits is divisible by 11.

Examples

Example 1: 3,762

Compute alternating sum:

• $2 - 6 + 7 - 3 = 0$

Since $0$ is divisible by 11 → 3,762 is divisible by 11.

Example 2: 84,5172

Compute alternating sum:

• $2 - 7 + 1 - 5 + 4 - 8 = -13$

Since $-13$ is not divisible by 11 → not divisible by 11.

Example 3: 121

• $1 - 2 + 1 = 0$
• So 121 is divisible by 11 (indeed $121 = 11^2$).

Divisibility by 4, 8, 25, and 125: Looking at the Last Few Digits

These rules come from the fact that powers of 10 eventually become 0 modulo these numbers.

Divisibility by 4

Key fact

• $100 \equiv 0 \pmod{4}$
• So only the last two digits matter.

Rule

• A number is divisible by 4 iff its last two digits form a number divisible by 4.

Examples

• 316 → last two digits: 16 → $16 \div 4 = 4$ → divisible
• 2,748 → last two digits: 48 → divisible
• 1,253 → last two digits: 53 → not divisible

Divisibility by 8

Key fact

• $1000 \equiv 0 \pmod{8}$
• So only the last three digits matter.

Rule

• A number is divisible by 8 iff its last three digits form a number divisible by 8.

Examples

• 5,416 → last three digits: 416 → $416 \div 8 = 52$ → divisible
• 12,304 → last three digits: 304 → divisible
• 7,129 → last three digits: 129 → not divisible

Divisibility by 25

Key fact

• $100 \equiv 0 \pmod{25}$
• So only the last two digits matter.

Rule

• A number is divisible by 25 iff its last two digits are 00, 25, 50, or 75.

Examples

• 3,525 → ends in 25 → divisible
• 1,450 → ends in 50 → divisible
• 2,718 → ends in 18 → not divisible

Divisibility by 125

Key fact

• $1000 \equiv 0 \pmod{125}$
• So only the last three digits matter.

Rule

• A number is divisible by 125 iff its last three digits form a number divisible by 125.

Examples

• 6,250 → last three digits: 250 → $250 = 2 \cdot 125$ → divisible
• 9,375 → last three digits: 375 → divisible
• 4,812 → last three digits: 812 → not divisible

General Strategy: Building Your Own Divisibility Tests

To create a divisibility test for any number $d$:

1. Compute $10 \bmod d$, $10^2 \bmod d$, $10^3 \bmod d$, etc.
2. Look for patterns:
   • Does $10^k \equiv 0$?
   • Does $10^k \equiv 1$ or $-1$?
3. Rewrite $$n = a_0 + 10a_1 + 10^2 a_2 + \cdots$$ using these congruences.
4. Simplify to get a rule involving:
   • last digits,
   • digit sums,
   • alternating sums,
   • or other combinations.

This method works for any divisor.

Common Misconceptions and Pitfalls

• Misconception: Divisibility rules are arbitrary tricks.
  • They follow directly from congruence.
• Pitfall: Forgetting that congruence works digit‑by‑digit.
• Misconception: The sum‑of‑digits rule works for all numbers.
  • It works only when $10 \equiv 1 \pmod{d}$.
• Pitfall: Using the wrong number of digits (e.g., checking only the last two digits for divisibility by 8).

Applications in Problem‑Solving and Number Theory

• Quick mental checks when simplifying fractions.
• Contest math: spotting divisibility saves time.
• Cryptography: modular arithmetic is foundational.
• Computer science: hashing and checksums rely on modular ideas.
• Number theory: divisibility is central to deeper results like the Euclidean Algorithm.

Exercises

1. Explain why only the last digit matters for divisibility by 2.

   Solution

   Explain why only the last digit matters for divisibility by 2.

   • Any number $n$ can be written as $$n = a_0 + 10a_1 + 10^2 a_2 + \cdots.$$
   • Modulo 2, we have $10 \equiv 0$, so $10a_1, 10^2 a_2, \dots$ are all divisible by 2.
   • Therefore, $$n \equiv a_0 \pmod{2}.$$
   • This means $n$ is divisible by 2 iff its last digit $a_0$ is even.
2. Use congruence to prove the sum‑of‑digits rule for 9.

   Solution

   Use congruence to prove the sum‑of‑digits rule for 9.

   • Write $$n = a_0 + 10a_1 + 10^2 a_2 + \cdots.$$
   • Since $10 \equiv 1 \pmod{9}$, we have $10^k \equiv 1^k \equiv 1 \pmod{9}$.
   • Therefore, $$n \equiv a_0 + a_1 + a_2 + \cdots \pmod{9}.$$
   • So $n$ is divisible by 9 iff the sum of its digits is divisible by 9.
3. Determine whether $57{,}321$ is divisible by 3, 9, or both.

   Solution

   Determine whether $57{,}321$ is divisible by 3, 9, or both.

   • Digit sum: $$5 + 7 + 3 + 2 + 1 = 18.$$
   • 18 is divisible by 3 and by 9.
   • Therefore, $57{,}321$ is divisible by both 3 and 9.
4. Compute the alternating sum of digits for $84{,}517$ and determine whether it is divisible by 11.

   Solution

   Compute the alternating sum of digits for $84{,}517$ and determine whether it is divisible by 11.

   • Write digits from right to left: 7, 1, 5, 4, 8.
   • Alternating sum (starting with $+$ on the last digit): $$7 - 1 + 5 - 4 + 8 = 15.$$
   • 15 is not divisible by 11.
   • Therefore, $84{,}517$ is not divisible by 11.
5. Explain why only the last two digits matter for divisibility by 4.

   Solution

   Explain why only the last two digits matter for divisibility by 4.

   • Any number $n$ can be written as $$n = 100k + d,$$

   where $d$ is the number formed by the last two digits.

   • Since $100 \equiv 0 \pmod{4}$, the term $100k$ is always divisible by 4.
   • Thus, $$n \equiv d \pmod{4}.$$
   • So $n$ is divisible by 4 iff $d$ (the last two digits) is divisible by 4.
6. Determine whether $123{,}456$ is divisible by 8.

   Solution

   Determine whether $123{,}456$ is divisible by 8.

   • Only the last three digits matter: 456.
   • Compute $456 \div 8$:
     • $8 \cdot 50 = 400$
     • $456 - 400 = 56$
     • $8 \cdot 7 = 56$
     • So $456 = 8 \cdot 57$.
   • Therefore, 456 is divisible by 8, and so is $123{,}456$.
7. Create a divisibility test for 7 using the fact that $10 \equiv 3 \pmod{7}$.

   Solution

   Create a divisibility test for 7 using the fact that $10 \equiv 3 \pmod{7}$.

   One simple approach:

   • Write $n = a_0 + 10a_1 + 10^2 a_2 + \cdots$.
   • Modulo 7, $10 \equiv 3$, so $10^2 \equiv 3^2 = 9 \equiv 2$, etc.
   • A practical test (one common version):
     • Rule: Take the last digit, double it, and subtract from the rest of the number.
     • If the result is divisible by 7 (possibly after repeating the process), then the original number is divisible by 7.

   Example:

   • Test 203:
     • Last digit: 3, rest: 20.
     • Compute $20 - 2\cdot 3 = 20 - 6 = 14$.
     • 14 is divisible by 7 → 203 is divisible by 7.
8. Show that a number is divisible by 25 iff its last two digits form a number divisible by 25.

   Solution

   Show that a number is divisible by 25 iff its last two digits form a number divisible by 25.

   • Write $$n = 100k + d,$$

   where $d$ is the number formed by the last two digits.

   • Since $100 \equiv 0 \pmod{25}$, we have $$n \equiv d \pmod{25}.$$
   • Therefore, $n$ is divisible by 25 iff $d$ is divisible by 25.
   • The only two‑digit multiples of 25 are 00, 25, 50, and 75.
9. Determine whether $99{,}999$ is divisible by 11.

   Solution

   Determine whether $99{,}999$ is divisible by 11.

   • Digits: 9, 9, 9, 9, 9.
   • Alternating sum (from right): $$9 - 9 + 9 - 9 + 9 = 9.$$
   • 9 is not divisible by 11.
   • Therefore, $99{,}999$ is not divisible by 11.
10. True or false: If $10 \equiv 1 \pmod{d}$, then the sum‑of‑digits test works for $d$.

    Solution

    True or false: If $10 \equiv 1 \pmod{d}$, then the sum‑of‑digits test works for $d$.

    • If $10 \equiv 1 \pmod{d}$, then $10^k \equiv 1^k \equiv 1 \pmod{d}$.
    • So for $$n = a_0 + 10a_1 + 10^2 a_2 + \cdots,$$

    we have $$n \equiv a_0 + a_1 + a_2 + \cdots \pmod{d}.$$

    • Thus $n \equiv 0 \pmod{d}$ iff the sum of its digits is $\equiv 0 \pmod{d}$.

    Answer: True.